SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Bisection (software engineering)</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Bisection (software engineering)</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">For other uses, see <a href="Bisect_(disambiguation)" class="mw-redirect mw-disambig" title="Bisect (disambiguation)">Bisect</a>.</div>

<p><b>Bisection</b> is a method used in <a href="Software_development" title="Software development">software development</a> to identify <a href="Patch_(computing)" title="Patch (computing)">change sets</a> that result in a specific behavior change. It is mostly employed for finding the patch that introduced a <a href="Software_bug" title="Software bug">bug</a>. Another application area is finding the patch that indirectly fixed a bug.

</p>

<div class="mw-heading mw-heading2"><h2 id="Overview">Overview</h2></div>

<p>The process of locating the <a href="Changeset" title="Changeset">changeset</a> that introduced a specific <a href="Software_regression" title="Software regression">regression</a> was described as "source change isolation" in 1997 by Brian Ness and Viet Ngo of <a href="Cray_Research" class="mw-redirect" title="Cray Research">Cray Research</a>. <a href="Regression_testing" title="Regression testing">Regression testing</a> was performed on Cray's <a href="Compiler" title="Compiler">compilers</a> in editions comprising one or more changesets. Editions with known regressions could not be validated until developers addressed the problem. Source change isolation narrowed the cause to a single changeset that could then be excluded from editions, unblocking them with respect to this problem, while the author of the change worked on a fix. Ness and Ngo outlined <a href="Linear_search" title="Linear search">linear search</a> and <a href="Binary_search" title="Binary search">binary search</a> methods of performing this isolation.<sup id="cite_ref-Ness_97_1-0" class="reference"><a href="#cite_note-Ness_97-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p><p>Code bisection has the goal of minimizing the effort to find a specific change set.

It employs a <a href="Divide_and_conquer_algorithm" class="mw-redirect" title="Divide and conquer algorithm">divide and conquer algorithm</a> that

depends on having access to the code history which is usually preserved by

<a href="Revision_control" class="mw-redirect" title="Revision control">revision control</a> in a <a href="Repository_(version_control)" title="Repository (version control)">code repository</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Bisection_method">Bisection method</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Code_bisection_algorithm">Code bisection algorithm</h3></div>

<p>Code history has the structure of a <a href="Directed_acyclic_graph" title="Directed acyclic graph">directed acyclic graph</a> which can be <a href="Topological_ordering" class="mw-redirect" title="Topological ordering">topologically sorted</a>. This makes it possible to use a divide and conquer search algorithm which:

</p>

<ul><li>splits up the <a href="Computational_geometry#Geometric_query_problems" title="Computational geometry">search space</a> of candidate revisions</li>

<li>tests for the behavior in question</li>

<li>reduces the search space depending on the test result</li>

<li>re-iterates the steps above until a range with at most one bisectable <a href="Candidate_solution" class="mw-redirect" title="Candidate solution">patch candidate</a> remains</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Algorithmic_complexity">Algorithmic complexity</h3></div>

<p>Bisection is in <a href="L_(complexity)" title="L (complexity)">LSPACE</a> having an <a href="Analysis_of_algorithms" title="Analysis of algorithms">algorithmic complexity</a> of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log N)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log N)}</annotation>

</semantics>

</math></span><img src="./14eea297b4387decf341763c39dc038e05744272.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.005ex; height:2.843ex;" alt="{\displaystyle O(\log N)}" loading="lazy"></span> with <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math></span><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"></span> denoting the number of revisions in the search space, and is similar to a <a href="Binary_search" title="Binary search">binary search</a>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Desirable_repository_properties">Desirable repository properties</h3></div>

<p>For code bisection it is desirable that each revision in the search space can be built and tested independently.

</p>

<div class="mw-heading mw-heading3"><h3 id="Monotonicity">Monotonicity</h3></div>

<p>For the bisection algorithm to identify a single changeset which caused the behavior being tested to change, the behavior must change <a href="Monotonic_function" title="Monotonic function">monotonically</a> across the search space. For a Boolean function such as a pass/fail test, this means that it only changes once across all changesets between the start and end of the search space.

</p><p>If there are multiple changesets across the search space where the behavior being tested changes between false and true, then the bisection algorithm will find one of them, but it will not necessarily be the <a href="Root_cause_analysis" title="Root cause analysis">root cause</a> of the change in behavior between the start and the end of the search space. The root cause could be a different changeset, or a combination of two or more changesets across the search space. To help deal with this problem, automated tools allow specific changesets to be ignored during a bisection search.

</p>

<div class="mw-heading mw-heading2"><h2 id="Automation_support">Automation support</h2></div>

<p>Although the bisection method can be completed manually, one of its main advantages is that it can be easily automated.<sup id="cite_ref-Ness_97_1-1" class="reference"><a href="#cite_note-Ness_97-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> It can thus fit into existing <a href="Test_automation" title="Test automation">test automation</a> processes: failures in exhaustive automated regression tests can trigger automated bisection to localize faults. Ness and Ngo focused on its potential in Cray's <a href="Continuous_delivery" title="Continuous delivery">continuous delivery</a>-style environment in which the automatically isolated bad changeset could be automatically excluded from builds.<sup id="cite_ref-Zeller_99_2-0" class="reference"><a href="#cite_note-Zeller_99-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p><p>The revision control systems <a href="Fossil_SCM" class="mw-redirect" title="Fossil SCM">Fossil</a>, <a href="Git_(software)" class="mw-redirect" title="Git (software)">Git</a> and <a href="Mercurial" title="Mercurial">Mercurial</a> have built-in functionality for code bisection.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> The user can start a bisection session with a specified range of revisions from which the revision control system proposes a revision to test, the user tells the system whether the revision tested as "good" or "bad", and the process repeats until the specific "bad" revision has been identified. Other revision control systems, such as <a href="Bazaar_(software)" class="mw-redirect" title="Bazaar (software)">Bazaar</a> or <a href="Apache_Subversion" title="Apache Subversion">Subversion</a>, support bisection through plugins<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> or external scripts.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup>

</p><p><a href="Phoronix_Test_Suite" title="Phoronix Test Suite">Phoronix Test Suite</a> can do bisection automatically to find performance regressions.

</p>

<ul><li><a href="Delta_debugging" title="Delta debugging">Delta debugging</a> (generalization of finding a minimal cause of a bug)</li>

<li><a href="Annotation#Source_control" title="Annotation">Annotation § Source control</a> (determining changesets that edited a line in a file)</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFNessNgo1997" class="citation conference cs1">Ness, Brian; Ngo, Viet (1997). <i>Regression containment through source change isolation</i>. Computer Software and Applications Conference. IEEE. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FCMPSAC.1997.625082">10.1109/CMPSAC.1997.625082</a>.</cite></span>

</li>

<li id="cite_note-Zeller_99-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-Zeller_99_2-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFZeller1999" class="citation conference cs1">Zeller, Andreas (1999). <i>Yesterday, my program worked. Today, it does not. Why?</i>. European Software Engineering Conference. Toulouse, France. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F318774.318946">10.1145/318774.318946</a></span>.</cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.fossil-scm.org/fossil/help/bisect">"Fossil: Help: bisect"</a>. <i>www.fossil-scm.org</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2020-09-03</span></span>.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://git-scm.com/docs/git-bisect">"git-bisect(1)"</a>. <i>git-scm.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2017-08-05</span></span>.</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.selenic.com/mercurial/hg.1.html#bisect">"hg"</a>. <i>Selenic.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2017-01-09</span></span>.</cite></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://doc.bazaar.canonical.com/plugins/en/bisect-plugin.html">"bisect - Find the revision introducing a bug using a binary search — Bazaar 2.8.0dev1 documentation"</a>. <i>Doc.bazaar.canonical.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2017-01-09</span></span>.</cite></span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://metacpan.org/dist/App-SVN-Bisect/view/bin/svn-bisect">"svn-bisect"</a>. <i>Metacpan.org</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2022-08-03</span></span>.</cite></span>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2023-01-30" href="https://en.wikipedia.org/wiki/?title=Bisection_(software_engineering)&oldid=1136432968">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>